
/**
 * basic version of a tree
 * mind: all searching in the tree relies on equality (===)
 * and NOT identity!
 * 
 * @param <T> Generic Type.
 * @author Lukas Koell
 * @author David Medenjak
 * @author Johannes Riedmann
 */
public abstract class Tree<T> {

    /**
     * the root node
     */
    protected Node<T> root;

    /**
     * looks up node in the tree and returns an iterator
     * for the node including its whole subtree
     * @param node Node to look for.
     * @return Returns Iterator over subtree of node, if found, else null.
     */
    public TreeIter<T> contains(T node) {
        Iter<Boolean> boolTree = this.search(node);
        if (boolTree == null) {
            return null;
        }
        
        Node<T> currentNode = root;
        
        while(currentNode.getValue() != node) { //iterate to node
            if (currentNode.getLeftChild() != null &&
                    currentNode.getLeftChild().contains(node)) {
                currentNode = currentNode.getLeftChild();
            } else if (currentNode.getRightChild() != null &&
                    currentNode.getRightChild().contains(node)) {
                currentNode = currentNode.getRightChild();
            }
        }
        
        ReplaceableTree<T> tree = new ReplaceableTree<T>();
        tree.setRoot(currentNode);
        
        return tree.iterator().down();
    }

    /**
     * @return a _NEW_ iterator for this tree
     */
    public TreeIter<T> iterator() {
        return contains(getRoot().getValue());
    }

    /**
     * searches node in the tree and returns an iterator
     * of boolean values. false means: go left, true means: go right
     * @param node Node to look for.
     * @return Returns iterator of booleans.
     */
    public Iter<Boolean> search(T node) {
        Tree<Boolean> boolTree = new ReplaceableTree<Boolean>();
        Node<T> currentNode = getRoot();

        if (currentNode.getValue() == node) {   //if currentNode is root, return null
            return null;
        }

        while (currentNode.getValue() != node) {
            if (currentNode.getLeftChild() != null
                    && currentNode.getLeftChild().contains(node)) {
                boolTree.add(false);
                currentNode = currentNode.getLeftChild();
            } else if (currentNode.getRightChild() != null
                    && currentNode.getRightChild().contains(node)) {
                boolTree.add(true);
                currentNode = currentNode.getRightChild();
            }
        }

        return boolTree.iterator();
    }

    /**
     * adds a node to the tree
     * implementation depends on subclass
     * @param node
     */
    public abstract void add(T node);

    /**
     * Returns a text representation of the tree.
     */
    @Override
    public String toString() {
        Iter<T> iter = new TreeIterator<T>(this);
        String text = "";
        while (iter.hasNext()) {
            text = iter.next().toString();
        }
        return text;
    }

    /**
     * @return the root
     */
    public Node<T> getRoot() {
        return root;
    }

    /**
     * @param root the root to set
     */
    public void setRoot(Node<T> root) {
        this.root = root;
    }
}
